#include <iostream>

struct Node {
    int val;
    Node *next;
};

Node *rfind_k(Node head, int k)
{
    Node *pk = head.next;

    while (k-- > 0 && pk != NULL) {
        pk = pk->next;
    }

    Node *p = head.next;

    while(pk != NULL) {
        p = p->next;
        pk = pk->next;
    }

    return p;
}

void link(Node *nodes, int pre, int next)
{
    if (next != -1) {
        nodes[pre].next = &nodes[next];
    } else {
        nodes[pre].next = NULL;
    }
}

int main(int argc, const char *argv[])
{
    Node test[10] = {
        {1, NULL},
        {2, NULL},
        {3, NULL},
        {4, NULL},
        {5, NULL},
        {6, NULL},
        {7, NULL},
        {8, NULL},
        {9, NULL},
        {10, NULL}
    };
    link(test, 0, 1);
    link(test, 1, 2);
    link(test, 2, 3);
    link(test, 3, 4);
    link(test, 4, 5);
    link(test, 5, 6);
    link(test, 6, 7);
    link(test, 7, 8);
    link(test, 8, 9);
    link(test, 9, -1);

    Node head; head.next = test;
    std::cout << "the rfind -1 is " << rfind_k(head, -1) << std::endl;
    std::cout << "the rfind 0 is " << rfind_k(head, 0) << std::endl;
    std::cout << "the rfind 1 is " << rfind_k(head, 1)->val << std::endl;
    std::cout << "the rfind 5 is " << rfind_k(head, 5)->val << std::endl;
    std::cout << "the rfind 9 is " << rfind_k(head, 9)->val << std::endl;
    std::cout << "the rfind 10 is " << rfind_k(head, 10)->val << std::endl;
    std::cout << "the rfind 20 is " << rfind_k(head, 11)->val << std::endl;
    return 0;
}
